//
// Description: 5966. 还原原数组
// Created by Loading on 2021/12/26.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> recoverArray(vector<int> &nums) {
    int N = nums.size();
    sort(nums.begin(), nums.end());
    unordered_map<int, int> m;
    // 统计次数
    for (auto x : nums) {
        m[x]++;
    }

    vector<int> vk;
    // 找出所有的 k 的二倍
    for (int i = 1; i < N / 2 + 1; ++i) {
        int double_k = nums[i] - nums[0];
        if (double_k && double_k % 2 == 0) {
            vk.emplace_back(double_k);
        }
    }

    for (auto dk : vk) {
        auto tmp_m = m;
        vector<int> res;
        // 枚举所有的 lower 数组中的元素，lower[i] + dk = higher[i]
        for (auto x : nums) {
            if (tmp_m[x] > 0) {
                if (tmp_m.find(x + dk) == tmp_m.end() || tmp_m[x + dk] <= 0) {
                    break;
                } else {
                    // 找到一组，次数对应减一
                    tmp_m[x]--;
                    tmp_m[x + dk]--;
                    res.emplace_back(x + dk / 2);
                }
            }
        }
        if (res.size() == N / 2) {
            return res;
        }
    }

    return {};
}

int main() {
    vector<int> arr = {2, 10, 6, 4, 8, 12};
    vector<int> res = recoverArray(arr);
    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}